Condition number estimation of preconditioned matrices

櫛田 慶幸

PLOS ONE (Internet), 10(3), p.e0122331_1 - e0122331_16, 2015/03

https://doi.org/10.1371/journal.pone.0122331

本論文では前処理済み行列の条件数を推定する新しい手法を開発した。これにより、現在主流の線形連立一次方程式解法であるクリロフ部分空間法の収束性を向上させ、シミュレーションの時間を短縮することが可能となる。従来、前処理済み行列の条件数を推定するためには、(1)密行列になることを受け入れ実際に前処理行列を作用させるか、(2)ランチョスコネクションと呼ばれるランチョス法に基づき固有値を推定する方法が用いられてきた。しかしながら、(1)はメモリ使用量が膨大になるため実際のシミュレーションで使われる規模の行列では事実上不可能であり、(2)は本論文で示すように計算誤差のため実用には程遠い。このため、本論文ではある行列の逆行列の行列ノルムを推定するHagerの方法に基づき、前処理済み行列の条件数を推定するアルゴリズムを開発した。Matrix Marketから得らるサンプル行列や、ポワソン方程式をFEMで離散化した行列を用いて精度検証を行ったところ、ランチョスコネクションが意味のない推定値をだす条件であっても、新手法は安定していることが示された。また、計算量およびメモリ使用量の解析を行い、計算量は実際のシミュレーションに必要な量の4倍が必要となるが、メモリ使用量についてはほぼ同量しか必要とならないことが示された。これにより、開発した新手法が従来手法(1),(2)の問題点を克服したと言える。